package com.example.shirotest.study;

public class MigonTest {

    public static void main(String[] args) {
        //先创建一个二维数组，模拟迷宫
        //地图
        int[][] map = new int[8][7];
        //数字1表示墙
        //上下全部设置为1
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }

        //左右全部设置为1
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }

        //设置挡板
        map[3][1] = 1;
        map[3][2] = 1;

        map[3][4] = 1;
        map[3][5] = 1;

        map[5][3] = 1;
        map[5][4] = 1;
        map[5][5] = 1;

        //输出地图
        System.out.println("Show the map grid:");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.printf(map[i][j]+" ");
            }
            System.out.println();
        }

        //开始节点
        setWay(map,2,4);
        //输出地图
        System.out.println("Show the way in the map grid:");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.printf(map[i][j]+" ");
            }
            System.out.println();
        }

    }


    //使用递归回溯给小球找路
    //约定说明
    //1.map 表示地图
    //2.i,j 表示从地图的哪个位置开始出发（i,j） => (行，列表)
    //3.如果小球能到map[6][5]位置，则说明通路找到
    //4.约定数组值 0-没有走过 1-墙 2-通路可走 3-走不通
    //5.走迷宫时，需要确定策略（小球摸索道路的方向）下->右->上->左，如果该点不通，在回溯
    /**
     * @param map  地图数组
     * @param i    开始位置 i
     * @param j    开始位置 j
     * @return     如果找到通路，就返回true,否则返回false
     */
    public static boolean setWay(int[][] map,int i,int j){
        if(map[6][5]==2){ //通路已经找到
            return true;
        }else {
            //如果当前这个点还没有走过
            if(map[i][j]==0){
                map[i][j] = 2;//假定该点是可以走通
                //按照策略 下->右->上->左
                if(setWay(map,i+1,j)){ //向下走
                    return true;
                } else if (setWay(map,i,j+1)) { //向右
                    return true;
                } else if (setWay(map,i-1,j)) {  //向上
                    return true;
                } else if (setWay(map,i,j-1)) {  //向左
                    return true;
                }else {
                    //说明该点是走不通，是死路
                    map[i][j] = 3;
                    return false;
                }
            }else {   // 可能是 1,2,3
                return false;
            }
        }

    }




}
